package com.leetcode.partition3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/12/14 21:12
 */
public class LC210课程表II {

    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        return topological(numCourses, prerequisites);
    }

    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        System.out.println(Arrays.toString(findOrder(numCourses, prerequisites)));
    }

    private static int[] topological(int numCourses, int[][] prerequisites) {
        List<Integer> answer = new ArrayList<>();
        int m = prerequisites.length, index = 0;
        int[] head = new int[numCourses], element = new int[m], next = new int[m], inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) head[i] = -1;
        for (int[] prerequisite : prerequisites) {
            int u = prerequisite[1], v = prerequisite[0];
            element[index] = v;
            next[index] = head[u];
            head[u] = index++;
            inDegree[v]++;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.addLast(i);
        }
        while (!queue.isEmpty()) {
            int u = queue.pollFirst();
            answer.add(u);
            for (int i = head[u]; i != -1; i = next[i]) {
                int v = element[i];
                inDegree[v]--;
                if (inDegree[v] == 0) queue.addLast(v);
            }
        }
        return answer.size() == numCourses ? answer.stream().mapToInt(val -> val).toArray() : new int[0];
    }
}
